home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / access / nbtree / nbtsearch.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-27  |  31.5 KB  |  1,140 lines
  1. /*
  2.  *  btsearch.c -- search code for postgres btrees.
  3.  */
  4.  
  5. #include "tmp/c.h"
  6. #include "tmp/postgres.h"
  7.  
  8. #include "storage/bufmgr.h"
  9. #include "storage/bufpage.h"
  10. #include "storage/page.h"
  11.  
  12. #include "utils/log.h"
  13. #include "utils/rel.h"
  14. #include "utils/excid.h"
  15.  
  16. #include "access/heapam.h"
  17. #include "access/genam.h"
  18. #include "access/ftup.h"
  19. #include "access/skey.h"
  20. #include "access/sdir.h"
  21. #include "access/nbtree.h"
  22.  
  23. RcsId("$Header: /private/postgres/src/access/nbtree/RCS/nbtsearch.c,v 1.24 1992/08/06 00:10:37 mao Exp $");
  24.  
  25. /*
  26.  *  _bt_search() -- Search for a scan key in the index.
  27.  *
  28.  *    This routine is actually just a helper that sets things up and
  29.  *    calls a recursive-descent search routine on the tree.
  30.  */
  31.  
  32. BTStack
  33. _bt_search(rel, keysz, scankey, bufP)
  34.     Relation rel;
  35.     int keysz;
  36.     ScanKey scankey;
  37.     Buffer *bufP;
  38. {
  39.     *bufP = _bt_getroot(rel, BT_READ);
  40.     return (_bt_searchr(rel, keysz, scankey, bufP, (BTStack) NULL));
  41. }
  42.  
  43. /*
  44.  *  _bt_searchr() -- Search the tree recursively for a particular scankey.
  45.  */
  46.  
  47. BTStack
  48. _bt_searchr(rel, keysz, scankey, bufP, stack_in)
  49.     Relation rel;
  50.     int keysz;
  51.     ScanKey scankey;
  52.     Buffer *bufP;
  53.     BTStack stack_in;
  54. {
  55.     BTStack stack;
  56.     OffsetIndex offind;
  57.     Page page;
  58.     BTPageOpaque opaque;
  59.     BlockNumber par_blkno;
  60.     BlockNumber blkno;
  61.     ItemId itemid;
  62.     BTItem btitem;
  63.     BTItem item_save;
  64.     int item_nbytes;
  65.     IndexTuple itup;
  66.     IndexTuple itup_save;
  67.  
  68.     /* if this is a leaf page, we're done */
  69.     page = BufferGetPage(*bufP, 0);
  70.     opaque = (BTPageOpaque) PageGetSpecialPointer(page);
  71.     if (opaque->btpo_flags & BTP_LEAF)
  72.     return (stack_in);
  73.  
  74.     /*
  75.      *  Find the appropriate item on the internal page, and get the child
  76.      *  page that it points to.
  77.      */
  78.  
  79.     par_blkno = BufferGetBlockNumber(*bufP);
  80.     offind = _bt_binsrch(rel, *bufP, keysz, scankey, BT_DESCENT);
  81.     itemid = PageGetItemId(page, offind);
  82.     btitem = (BTItem) PageGetItem(page, itemid);
  83.     itup = &(btitem->bti_itup);
  84.     blkno = ItemPointerGetBlockNumber(&(itup->t_tid));
  85.  
  86.     /*
  87.      *  We need to save the bit image of the index entry we chose in the
  88.      *  parent page on a stack.  In case we split the tree, we'll use this
  89.      *  bit image to figure out what our real parent page is, in case the
  90.      *  parent splits while we're working lower in the tree.  See the paper
  91.      *  by Lehman and Yao for how this is detected and handled.  (We use
  92.      *  unique OIDs to disambiguate duplicate keys in the index -- Lehman
  93.      *  and Yao disallow duplicate keys).
  94.      */
  95.  
  96.     item_nbytes = ItemIdGetLength(itemid);
  97.     item_save = (BTItem) palloc(item_nbytes);
  98.     bcopy((char *) btitem, (char *) item_save, item_nbytes);
  99.     stack = (BTStack) palloc(sizeof(BTStackData));
  100.     stack->bts_blkno = par_blkno;
  101.     stack->bts_offset = offind;
  102.     stack->bts_btitem = item_save;
  103.     stack->bts_parent = stack_in;
  104.  
  105.     /* drop the read lock on the parent page and acquire one on the child */
  106.     _bt_relbuf(rel, *bufP, BT_READ);
  107.     *bufP = _bt_getbuf(rel, blkno, BT_READ);
  108.  
  109.     /*
  110.      *  Race -- the page we just grabbed may have split since we read its
  111.      *  pointer in the parent.  If it has, we may need to move right to its
  112.      *  new sibling.  Do that.
  113.      */
  114.  
  115.     *bufP = _bt_moveright(rel, *bufP, keysz, scankey, BT_READ);
  116.  
  117.     /* okay, all set to move down a level */
  118.     return (_bt_searchr(rel, keysz, scankey, bufP, stack));
  119. }
  120.  
  121. /*
  122.  *  _bt_moveright() -- move right in the btree if necessary.
  123.  *
  124.  *    When we drop and reacquire a pointer to a page, it is possible that
  125.  *    the page has changed in the meanwhile.  If this happens, we're
  126.  *    guaranteed that the page has "split right" -- that is, that any
  127.  *    data that appeared on the page originally is either on the page
  128.  *    or strictly to the right of it.
  129.  *
  130.  *    This routine decides whether or not we need to move right in the
  131.  *    tree by examining the high key entry on the page.  If that entry
  132.  *    is strictly less than one we expect to be on the page, then our
  133.  *    picture of the page is incorrect and we need to move right.
  134.  *
  135.  *    On entry, we have the buffer pinned and a lock of the proper type.
  136.  *    If we move right, we release the buffer and lock and acquire the
  137.  *    same on the right sibling.
  138.  */
  139.  
  140. Buffer
  141. _bt_moveright(rel, buf, keysz, scankey, access)
  142.     Relation rel;
  143.     Buffer buf;
  144.     int keysz;
  145.     ScanKey scankey;
  146.     int access;
  147. {
  148.     Page page;
  149.     PageNumber right;
  150.     BTPageOpaque opaque;
  151.     ItemId hikey;
  152.     ItemId itemid;
  153.     BlockNumber rblkno;
  154.  
  155.     page = BufferGetPage(buf, 0);
  156.     opaque = (BTPageOpaque) PageGetSpecialPointer(page);
  157.  
  158.     /* if we're on a rightmost page, we don't need to move right */
  159.     if (opaque->btpo_next == P_NONE)
  160.     return (buf);
  161.  
  162.     /* by convention, item 0 on non-rightmost pages is the high key */
  163.     hikey = PageGetItemId(page, 0);
  164.  
  165.     /*
  166.      *  If the scan key that brought us to this page is >= the high key
  167.      *  stored on the page, then the page has split and we need to move
  168.      *  right.
  169.      */
  170.  
  171.     if (_bt_skeycmp(rel, keysz, scankey, page, hikey,
  172.             BTGreaterEqualStrategyNumber)) {
  173.  
  174.     /* move right as long as we need to */
  175.     do {
  176.         /*
  177.          *  If this page consists of all duplicate keys (hikey and first
  178.          *  key on the page have the same value), then we don't need to
  179.          *  step right.
  180.          */
  181.         if (PageGetMaxOffsetIndex(page) > 0) {
  182.         itemid = PageGetItemId(page, 1);
  183.         if (_bt_skeycmp(rel, keysz, scankey, page, itemid,
  184.                 BTEqualStrategyNumber)) {
  185.             /* break is for the "move right" while loop */
  186.             break;
  187.         }
  188.         }
  189.  
  190.         /* step right one page */
  191.         rblkno = opaque->btpo_next;
  192.         _bt_relbuf(rel, buf, access);
  193.         buf = _bt_getbuf(rel, rblkno, access);
  194.         page = BufferGetPage(buf, 0);
  195.         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
  196.         hikey = PageGetItemId(page, 0);
  197.  
  198.     } while (opaque->btpo_next != P_NONE
  199.          && _bt_skeycmp(rel, keysz, scankey, page, hikey,
  200.                  BTGreaterEqualStrategyNumber));
  201.     }
  202.     return (buf);
  203. }
  204.  
  205. /*
  206.  *  _bt_skeycmp() -- compare a scan key to a particular item on a page using
  207.  *             a requested strategy (<, <=, =, >=, >).
  208.  *
  209.  *    We ignore the unique OIDs stored in the btree item here.  Those
  210.  *    numbers are intended for use internally only, in repositioning a
  211.  *    scan after a page split.  They do not impose any meaningful ordering.
  212.  *
  213.  *    The comparison is A <op> B, where A is the scan key and B is the
  214.  *    tuple pointed at by itemid on page.
  215.  */
  216.  
  217. bool
  218. _bt_skeycmp(rel, keysz, scankey, page, itemid, strat)
  219.     Relation rel;
  220.     Size keysz;
  221.     ScanKey scankey;
  222.     Page page;
  223.     ItemId itemid;
  224.     StrategyNumber strat;
  225. {
  226.     BTItem item;
  227.     IndexTuple indexTuple;
  228.     TupleDescriptor tupDes;
  229.     ScanKeyEntry entry;
  230.     int i;
  231.     Datum attrDatum;
  232.     Datum keyDatum;
  233.     bool compare;
  234.     bool isNull;
  235.  
  236.     item = (BTItem) PageGetItem(page, itemid);
  237.     indexTuple = &(item->bti_itup);
  238.  
  239.     tupDes = RelationGetTupleDescriptor(rel);
  240.  
  241.     /* see if the comparison is true for all of the key attributes */
  242.     for (i=1; i <= keysz; i++) {
  243.  
  244.     entry = &scankey->data[i-1];
  245.     attrDatum = IndexTupleGetAttributeValue(indexTuple,
  246.                         entry->attributeNumber,
  247.                         tupDes, &isNull);
  248.     keyDatum  = entry->argument;
  249.  
  250.     compare = _bt_invokestrat(rel, i, strat, keyDatum, attrDatum);
  251.     if (!compare)
  252.         return (false);
  253.     }
  254.  
  255.     return (true);
  256. }
  257.  
  258. /*
  259.  *  _bt_binsrch() -- Do a binary search for a key on a particular page.
  260.  *
  261.  *    The scankey we get has the compare function stored in the procedure
  262.  *    entry of each data struct.  We invoke this regproc to do the
  263.  *    comparison for every key in the scankey.  _bt_binsrch() returns
  264.  *    the OffsetIndex of the first matching key on the page, or the
  265.  *    OffsetIndex at which the matching key would appear if it were
  266.  *    on this page.
  267.  *
  268.  *    By the time this procedure is called, we're sure we're looking
  269.  *    at the right page -- don't need to walk right.  _bt_binsrch() has
  270.  *    no lock or refcount side effects on the buffer.
  271.  */
  272.  
  273. OffsetIndex
  274. _bt_binsrch(rel, buf, keysz, scankey, srchtype)
  275.     Relation rel;
  276.     Buffer buf;
  277.     int keysz;
  278.     ScanKey scankey;
  279.     int srchtype;
  280. {
  281.     TupleDescriptor itupdesc;
  282.     Page page;
  283.     BTPageOpaque opaque;
  284.     OffsetIndex low, mid, high;
  285.     bool match;
  286.     int result;
  287.  
  288.     page = BufferGetPage(buf, 0);
  289.     opaque = (BTPageOpaque) PageGetSpecialPointer(page);
  290.  
  291.     /* by convention, item 0 on any non-leftmost page is the high key */
  292.     if (opaque->btpo_next != P_NONE)
  293.     low = 1;
  294.     else
  295.     low = 0;
  296.  
  297.     high = PageGetMaxOffsetIndex(page);
  298.  
  299.     /*
  300.      *  Since for non-leftmost pages, the zeroeth item on the page is the
  301.      *  high key, there are two notions of emptiness.  One is if nothing
  302.      *  appears on the page.  The other is if nothing but the high key does.
  303.      *  The reason we test high <= low, rather than high == low, is that
  304.      *  after vacuuming there may be nothing *but* the high key on a page.
  305.      *  In that case, given the scheme above, low = 1 and high = 0.
  306.      */
  307.  
  308.     if (PageIsEmpty(page) || (opaque->btpo_next != P_NONE && high <= low))
  309.     return (low);
  310.  
  311.     itupdesc = RelationGetTupleDescriptor(rel);
  312.     match = false;
  313.  
  314.     while ((high - low) > 1) {
  315.     mid = low + ((high - low) / 2);
  316.     result = _bt_compare(rel, itupdesc, page, keysz, scankey, mid);
  317.  
  318.     if (result > 0)
  319.         low = mid;
  320.     else if (result < 0)
  321.         high = mid - 1;
  322.     else {
  323.         match = true;
  324.         break;
  325.     }
  326.     }
  327.  
  328.     /* if we found a match, we want to find the first one on the page */
  329.     if (match) {
  330.     return (_bt_firsteq(rel, itupdesc, page, keysz, scankey, mid));
  331.     } else {
  332.  
  333.     /*
  334.      *  We terminated because the endpoints got too close together.  There
  335.      *  are two cases to take care of.
  336.      *
  337.      *  For non-insertion searches on internal pages, we want to point at
  338.      *  the last key <, or first key =, the scankey on the page.  This
  339.      *  guarantees that we'll descend the tree correctly.
  340.      *
  341.      *  For all other cases, we want to point at the first key >=
  342.      *  the scankey on the page.  This guarantees that scans and
  343.      *  insertions will happen correctly.
  344.      */
  345.  
  346.     opaque = (BTPageOpaque) PageGetSpecialPointer(page);
  347.     if (!(opaque->btpo_flags & BTP_LEAF) && srchtype == BT_DESCENT) {
  348.  
  349.         /*
  350.          *  We want the last key <, or first key ==, the scan key.
  351.          */
  352.  
  353.         result = _bt_compare(rel, itupdesc, page, keysz, scankey, high);
  354.  
  355.         if (result == 0) {
  356.         return (_bt_firsteq(rel, itupdesc, page, keysz, scankey, high));
  357.         } else if (result > 0) {
  358.         return (high);
  359.         } else {
  360.         return (low);
  361.         }
  362.         /* NOTREACHED */
  363.     } else {
  364.  
  365.         /* we want the first key >= the scan key */
  366.         result = _bt_compare(rel, itupdesc, page, keysz, scankey, low);
  367.         if (result <= 0) {
  368.         return (low);
  369.         } else {
  370.         if (low == high)
  371.             return (low + 1);
  372.  
  373.         result = _bt_compare(rel, itupdesc, page, keysz, scankey, high);
  374.         if (result <= 0)
  375.             return (high);
  376.         else
  377.             return (high + 1);
  378.         }
  379.     }
  380.     /* NOTREACHED */
  381.     }
  382. }
  383.  
  384. OffsetIndex
  385. _bt_firsteq(rel, itupdesc, page, keysz, scankey, offind)
  386.     Relation rel;
  387.     TupleDescriptor itupdesc;
  388.     Page page;
  389.     Size keysz;
  390.     ScanKey scankey;
  391.     OffsetIndex offind;
  392. {
  393.     BTPageOpaque opaque;
  394.     OffsetIndex limit;
  395.  
  396.     opaque = (BTPageOpaque) PageGetSpecialPointer(page);
  397.  
  398.     /* skip the high key, if any */
  399.     if (opaque->btpo_next != P_NONE)
  400.     limit = 1;
  401.     else
  402.     limit = 0;
  403.  
  404.     /* walk backwards looking for the first key in the chain of duplicates */
  405.     while (offind > limit
  406.        && _bt_compare(rel, itupdesc, page,
  407.               keysz, scankey, offind - 1) == 0) {
  408.     offind--;
  409.     }
  410.  
  411.     return (offind);
  412. }
  413.  
  414. /*
  415.  *  _bt_compare() -- Compare scankey to a particular tuple on the page.
  416.  *
  417.  *    This routine returns:
  418.  *        -1 if scankey < tuple at offind;
  419.  *         0 if scankey == tuple at offind;
  420.  *        +1 if scankey > tuple at offind.
  421.  *
  422.  *    In order to avoid having to propogate changes up the tree any time
  423.  *    a new minimal key is inserted, the leftmost entry on the leftmost
  424.  *    page is less than all possible keys, by definition.
  425.  */
  426.  
  427. int
  428. _bt_compare(rel, itupdesc, page, keysz, scankey, offind)
  429.     Relation rel;
  430.     TupleDescriptor itupdesc;
  431.     Page page;
  432.     int keysz;
  433.     ScanKey scankey;
  434.     OffsetIndex offind;
  435. {
  436.     Datum datum;
  437.     BTItem btitem;
  438.     ItemId itemid;
  439.     IndexTuple itup;
  440.     BTPageOpaque opaque;
  441.     ScanKeyEntry entry;
  442.     AttributeNumber attno;
  443.     int result;
  444.     int i;
  445.     Boolean null;
  446.  
  447.     /*
  448.      *  If this is a leftmost internal page, and if our comparison is
  449.      *  with the first key on the page, then the item at that position is
  450.      *  by definition less than the scan key.
  451.      */
  452.  
  453.     opaque = (BTPageOpaque) PageGetSpecialPointer(page);
  454.     if (!(opaque->btpo_flags & BTP_LEAF)
  455.     && opaque->btpo_prev == P_NONE
  456.     && offind == 0) {
  457.         itemid = PageGetItemId(page, offind);
  458.  
  459.         /*
  460.          *  If the item on the page is equal to the scankey, that's
  461.          *  okay to admit.  We just can't claim that the first key on
  462.          *  the page is greater than anything.
  463.          */
  464.  
  465.         if (_bt_skeycmp(rel, keysz, scankey, page, itemid,
  466.                 BTEqualStrategyNumber)) {
  467.         return (0);
  468.         }
  469.         return (1);
  470.     }
  471.  
  472.     btitem = (BTItem) PageGetItem(page, PageGetItemId(page, offind));
  473.     itup = &(btitem->bti_itup);
  474.  
  475.     /*
  476.      *  The scan key is set up with the attribute number associated with each
  477.      *  term in the key.  It is important that, if the index is multi-key,
  478.      *  the scan contain the first k key attributes, and that they be in
  479.      *  order.  If you think about how multi-key ordering works, you'll
  480.      *  understand why this is.
  481.      *
  482.      *  We don't test for violation of this condition here.
  483.      */
  484.  
  485.     for (i = 1; i <= keysz; i++) {
  486.     entry = &(scankey->data[i - 1]);
  487.     attno = entry->attributeNumber;
  488.     datum = (Datum) IndexTupleGetAttributeValue(itup, attno,
  489.                             itupdesc, &null);
  490.     result = (int) (*(entry->func))(entry->argument, datum);
  491.  
  492.     /* if the keys are unequal, return the difference */
  493.     if (result != 0)
  494.         return (result);
  495.     }
  496.  
  497.     /* by here, the keys are equal */
  498.     return (0);
  499. }
  500.  
  501. /*
  502.  *  _bt_next() -- Get the next item in a scan.
  503.  *
  504.  *    On entry, we have a valid currentItemData in the scan, and a
  505.  *    read lock on the page that contains that item.  We do not have
  506.  *    the page pinned.  We return the next item in the scan.  On
  507.  *    exit, we have the page containing the next item locked but not
  508.  *    pinned.
  509.  */
  510.  
  511. RetrieveIndexResult
  512. _bt_next(scan, dir)
  513.     IndexScanDesc scan;
  514.     ScanDirection dir;
  515. {
  516.     Relation rel;
  517.     BTPageOpaque opaque;
  518.     Buffer buf;
  519.     Page page;
  520.     OffsetIndex offind, maxoff;
  521.     RetrieveIndexResult res;
  522.     BlockNumber blkno;
  523.     ItemPointer current;
  524.     ItemPointer iptr;
  525.     BTItem btitem;
  526.     IndexTuple itup;
  527.     BTScanOpaque so;
  528.  
  529.     rel = scan->relation;
  530.     so = (BTScanOpaque) scan->opaque;
  531.     current = &(scan->currentItemData);
  532.  
  533.     /*
  534.      *  XXX 10 may 91:  somewhere there's a bug in our management of the
  535.      *  cached buffer for this scan.  wei discovered it.  the following
  536.      *  is a workaround so he can work until i figure out what's going on.
  537.      */
  538.  
  539.     if (!BufferIsValid(so->btso_curbuf))
  540.     so->btso_curbuf = _bt_getbuf(rel, ItemPointerGetBlockNumber(current),
  541.                      BT_READ);
  542.  
  543.     /* we still have the buffer pinned and locked */
  544.     buf = so->btso_curbuf;
  545.     blkno = BufferGetBlockNumber(buf);
  546.  
  547.     /* step one tuple in the appropriate direction */
  548.     if (!_bt_step(scan, &buf, dir))
  549.     return ((RetrieveIndexResult) NULL);
  550.  
  551.     /* by here, current is the tuple we want to return */
  552.     offind = ItemPointerGetOffsetNumber(current, 0) - 1;
  553.     page = BufferGetPage(buf, 0);
  554.     btitem = (BTItem) PageGetItem(page, PageGetItemId(page, offind));
  555.     itup = &btitem->bti_itup;
  556.  
  557.     if (_bt_checkqual(scan, itup)) {
  558.     iptr = (ItemPointer) palloc(sizeof(ItemPointerData));
  559.     bcopy((char *) &(itup->t_tid), (char *) iptr, sizeof(ItemPointerData));
  560.     res = ItemPointerFormRetrieveIndexResult(current, iptr);
  561.  
  562.     /* remember which buffer we have pinned and locked */
  563.     so->btso_curbuf = buf;
  564.     } else {
  565.     ItemPointerSetInvalid(current);
  566.     so->btso_curbuf = InvalidBuffer;
  567.     _bt_relbuf(rel, buf, BT_READ);
  568.     res = (RetrieveIndexResult) NULL;
  569.     }
  570.  
  571.     return (res);
  572. }
  573.  
  574. /*
  575.  *  _bt_first() -- Find the first item in a scan.
  576.  *
  577.  *    We need to be clever about the type of scan, the operation it's
  578.  *    performing, and the tree ordering.  We return the RetrieveIndexResult
  579.  *    of the first item in the tree that satisfies the qualification
  580.  *    associated with the scan descriptor.  On exit, the page containing
  581.  *    the current index tuple is read locked and pinned, and the scan's
  582.  *    opaque data entry is updated to include the buffer.
  583.  */
  584.  
  585. RetrieveIndexResult
  586. _bt_first(scan, dir)
  587.     IndexScanDesc scan;
  588.     ScanDirection dir;
  589. {
  590.     Relation rel;
  591.     TupleDescriptor itupdesc;
  592.     Buffer buf;
  593.     Page page;
  594.     BTStack stack;
  595.     OffsetIndex offind, maxoff;
  596.     BTItem btitem;
  597.     IndexTuple itup;
  598.     ItemPointer current;
  599.     ItemPointer iptr;
  600.     BlockNumber blkno;
  601.     StrategyNumber strat;
  602.     RetrieveIndexResult res;
  603.     RegProcedure proc;
  604.     int result;
  605.     BTScanOpaque so;
  606.     ScanKeyData skdata;
  607.  
  608.     /* if we just need to walk down one edge of the tree, do that */
  609.     if (scan->scanFromEnd)
  610.     return (_bt_endpoint(scan, dir));
  611.  
  612.     rel = scan->relation;
  613.     itupdesc = RelationGetTupleDescriptor(scan->relation);
  614.     current = &(scan->currentItemData);
  615.     so = (BTScanOpaque) scan->opaque;
  616.  
  617.     /*
  618.      *  Okay, we want something more complicated.  What we'll do is use
  619.      *  the first item in the scan key passed in (which has been correctly
  620.      *  ordered to take advantage of index ordering) to position ourselves
  621.      *  at the right place in the scan.
  622.      */
  623.  
  624.     /*
  625.      *  XXX -- The attribute number stored in the scan key is the attno
  626.      *           in the heap relation.  We need to transmogrify this into
  627.      *         the index relation attno here.  For the moment, we have
  628.      *           hardwired attno == 1.
  629.      */
  630.     proc = index_getprocid(rel, 1, BTORDER_PROC);
  631.     ScanKeyEntryInitialize((ScanKeyEntry) &skdata, 0x0, 1, proc,
  632.                scan->keyData.data[0].argument);
  633.  
  634.     stack = _bt_search(rel, 1, &skdata, &buf);
  635.     _bt_freestack(stack);
  636.  
  637.     /* find the nearest match to the manufactured scan key on the page */
  638.     offind = _bt_binsrch(rel, buf, 1, &skdata, BT_DESCENT);
  639.     page = BufferGetPage(buf, 0);
  640.     maxoff = PageGetMaxOffsetIndex(page);
  641.  
  642.     if (offind > maxoff)
  643.     offind = maxoff;
  644.  
  645.     blkno = BufferGetBlockNumber(buf);
  646.     ItemPointerSet(current, 0, blkno, 0, offind + 1);
  647.  
  648.     /*
  649.      *  Now find the right place to start the scan.  Result is the
  650.      *  value we're looking for minus the value we're looking at
  651.      *  in the index.
  652.      */
  653.  
  654.     result = _bt_compare(rel, itupdesc, page, 1, &skdata, offind);
  655.     strat = _bt_getstrat(rel, 1, scan->keyData.data[0].procedure);
  656.  
  657.     switch (strat) {
  658.       case BTLessStrategyNumber:
  659.     if (result <= 0) {
  660.         do {
  661.         if (!_bt_twostep(scan, &buf, BackwardScanDirection))
  662.             break;
  663.  
  664.         offind = ItemPointerGetOffsetNumber(current, 0) - 1;
  665.         page = BufferGetPage(buf, 0);
  666.         result = _bt_compare(rel, itupdesc, page, 1, &skdata, offind);
  667.         } while (result <= 0);
  668.  
  669.         /* if this is true, the key we just looked at is gone */
  670.         if (result > 0)
  671.         (void) _bt_twostep(scan, &buf, ForwardScanDirection);
  672.     }
  673.     break;
  674.  
  675.       case BTLessEqualStrategyNumber:
  676.     if (result >= 0) {
  677.         do {
  678.         if (!_bt_twostep(scan, &buf, ForwardScanDirection))
  679.             break;
  680.  
  681.         offind = ItemPointerGetOffsetNumber(current, 0) - 1;
  682.         page = BufferGetPage(buf, 0);
  683.         result = _bt_compare(rel, itupdesc, page, 1, &skdata, offind);
  684.         } while (result >= 0);
  685.  
  686.         if (result < 0)
  687.         (void) _bt_twostep(scan, &buf, BackwardScanDirection);
  688.     }
  689.     break;
  690.  
  691.       case BTEqualStrategyNumber:
  692.     if (result != 0) {
  693.       _bt_relbuf(scan->relation, buf, BT_READ);
  694.       so->btso_curbuf = InvalidBuffer;
  695.       ItemPointerSetInvalid(&(scan->currentItemData));
  696.       return ((RetrieveIndexResult) NULL);
  697.     }
  698.     break;
  699.  
  700.       case BTGreaterEqualStrategyNumber:
  701.     if (result < 0) {
  702.         do {
  703.         if (!_bt_twostep(scan, &buf, BackwardScanDirection))
  704.             break;
  705.  
  706.         offind = ItemPointerGetOffsetNumber(current, 0) - 1;
  707.         page = BufferGetPage(buf, 0);
  708.         result = _bt_compare(rel, itupdesc, page, 1, &skdata, offind);
  709.         } while (result < 0);
  710.  
  711.         if (result > 0)
  712.         (void) _bt_twostep(scan, &buf, ForwardScanDirection);
  713.     }
  714.     break;
  715.  
  716.       case BTGreaterStrategyNumber:
  717.     if (result >= 0) {
  718.         do {
  719.         if (!_bt_twostep(scan, &buf, ForwardScanDirection))
  720.             break;
  721.  
  722.         offind = ItemPointerGetOffsetNumber(current, 0) - 1;
  723.         page = BufferGetPage(buf, 0);
  724.         result = _bt_compare(rel, itupdesc, page, 1, &skdata, offind);
  725.         } while (result >= 0);
  726.     }
  727.     break;
  728.     }
  729.  
  730.     /* okay, current item pointer for the scan is right */
  731.     offind = ItemPointerGetOffsetNumber(current, 0) - 1;
  732.     page = BufferGetPage(buf, 0);
  733.     btitem = (BTItem) PageGetItem(page, PageGetItemId(page, offind));
  734.     itup = &btitem->bti_itup;
  735.  
  736.     if (_bt_checkqual(scan, itup)) {
  737.     iptr = (ItemPointer) palloc(sizeof(ItemPointerData));
  738.     bcopy((char *) &(itup->t_tid), (char *) iptr, sizeof(ItemPointerData));
  739.     res = ItemPointerFormRetrieveIndexResult(current, iptr);
  740.  
  741.     /* remember which buffer we have pinned */
  742.     so->btso_curbuf = buf;
  743.     } else {
  744.     ItemPointerSetInvalid(current);
  745.     so->btso_curbuf = InvalidBuffer;
  746.     _bt_relbuf(rel, buf, BT_READ);
  747.     res = (RetrieveIndexResult) NULL;
  748.     }
  749.  
  750.     return (res);
  751. }
  752.  
  753. /*
  754.  *  _bt_step() -- Step one item in the requested direction in a scan on
  755.  *          the tree.
  756.  *
  757.  *    If no adjacent record exists in the requested direction, return
  758.  *    false.  Else, return true and set the currentItemData for the
  759.  *    scan to the right thing.
  760.  */
  761.  
  762. bool
  763. _bt_step(scan, bufP, dir)
  764.     IndexScanDesc scan;
  765.     Buffer *bufP;
  766.     ScanDirection dir;
  767. {
  768.     Page page;
  769.     BTPageOpaque opaque;
  770.     OffsetIndex offind, maxoff;
  771.     OffsetIndex start;
  772.     BlockNumber blkno;
  773.     BlockNumber obknum;
  774.     BTScanOpaque so;
  775.     ItemPointer current;
  776.     Relation rel;
  777.  
  778.     rel = scan->relation;
  779.     current = &(scan->currentItemData);
  780.     offind = ItemPointerGetOffsetNumber(current, 0) - 1;
  781.     page = BufferGetPage(*bufP, 0);
  782.     opaque = (BTPageOpaque) PageGetSpecialPointer(page);
  783.     so = (BTScanOpaque) scan->opaque;
  784.     maxoff = PageGetMaxOffsetIndex(page);
  785.  
  786.     /* get the next tuple */
  787.     if (ScanDirectionIsForward(dir)) {
  788.     if (offind < maxoff) {
  789.         offind++;
  790.     } else {
  791.  
  792.         /* if we're at end of scan, release the buffer and return */
  793.         if ((blkno = opaque->btpo_next) == P_NONE) {
  794.         _bt_relbuf(rel, *bufP, BT_READ);
  795.         ItemPointerSetInvalid(current);
  796.         *bufP = so->btso_curbuf = InvalidBuffer;
  797.         return (false);
  798.         } else {
  799.  
  800.         /* walk right to the next page with data */
  801.         _bt_relbuf(rel, *bufP, BT_READ);
  802.         for (;;) {
  803.             *bufP = _bt_getbuf(rel, blkno, BT_READ);
  804.             page = BufferGetPage(*bufP, 0);
  805.             opaque = (BTPageOpaque) PageGetSpecialPointer(page);
  806.             maxoff = PageGetMaxOffsetIndex(page);
  807.             if (opaque->btpo_next != P_NONE)
  808.             start = 1;
  809.             else
  810.             start = 0;
  811.  
  812.             if (!PageIsEmpty(page) && start <= maxoff) {
  813.             break;
  814.             } else {
  815.             blkno = opaque->btpo_next;
  816.             _bt_relbuf(rel, *bufP, BT_READ);
  817.             if (blkno == P_NONE) {
  818.                 *bufP = so->btso_curbuf = InvalidBuffer;
  819.                 ItemPointerSetInvalid(current);
  820.                 return (false);
  821.             }
  822.             }
  823.         }
  824.         offind = start;
  825.         }
  826.     }
  827.     } else if (ScanDirectionIsBackward(dir)) {
  828.  
  829.     /* remember that high key is item zero on non-rightmost pages */
  830.     if (opaque->btpo_next == P_NONE)
  831.         start = 0;
  832.     else
  833.         start = 1;
  834.  
  835.     if (offind > start) {
  836.         offind--;
  837.     } else {
  838.  
  839.         /* if we're at end of scan, release the buffer and return */
  840.         if ((blkno = opaque->btpo_prev) == P_NONE) {
  841.         _bt_relbuf(rel, *bufP, BT_READ);
  842.         *bufP = so->btso_curbuf = InvalidBuffer;
  843.         ItemPointerSetInvalid(current);
  844.         return (false);
  845.         } else {
  846.  
  847.         obknum = BufferGetBlockNumber(*bufP);
  848.  
  849.         /* walk right to the next page with data */
  850.         _bt_relbuf(rel, *bufP, BT_READ);
  851.         for (;;) {
  852.             *bufP = _bt_getbuf(rel, blkno, BT_READ);
  853.             page = BufferGetPage(*bufP, 0);
  854.             opaque = (BTPageOpaque) PageGetSpecialPointer(page);
  855.             maxoff = PageGetMaxOffsetIndex(page);
  856.  
  857.             /*
  858.              *  If the adjacent page just split, then we may have the
  859.              *  wrong block.  Handle this case.  Because pages only
  860.              *  split right, we don't have to worry about this failing
  861.              *  to terminate.
  862.              */
  863.  
  864.             while (opaque->btpo_next != obknum) {
  865.             blkno = opaque->btpo_next;
  866.             _bt_relbuf(rel, *bufP, BT_READ);
  867.             *bufP = _bt_getbuf(rel, blkno, BT_READ);
  868.             page = BufferGetPage(*bufP, 0);
  869.             opaque = (BTPageOpaque) PageGetSpecialPointer(page);
  870.             maxoff = PageGetMaxOffsetIndex(page);
  871.             }
  872.  
  873.             /* don't consider the high key */
  874.             if (opaque->btpo_next == P_NONE)
  875.             start = 0;
  876.             else
  877.             start = 1;
  878.  
  879.             /* anything to look at here? */
  880.             if (!PageIsEmpty(page) && maxoff >= start) {
  881.             break;
  882.             } else {
  883.             blkno = opaque->btpo_prev;
  884.             obknum = BufferGetBlockNumber(*bufP);
  885.             _bt_relbuf(rel, *bufP, BT_READ);
  886.             if (blkno == P_NONE) {
  887.                 *bufP = so->btso_curbuf = InvalidBuffer;
  888.                 ItemPointerSetInvalid(current);
  889.                 return (false);
  890.             }
  891.             }
  892.         }
  893.         offind = maxoff;
  894.         }
  895.     }
  896.     }
  897.     blkno = BufferGetBlockNumber(*bufP);
  898.     so->btso_curbuf = *bufP;
  899.     ItemPointerSet(current, 0, blkno, 0, offind + 1);
  900.  
  901.     return (true);
  902. }
  903.  
  904. /*
  905.  *  _bt_twostep() -- Move to an adjacent record in a scan on the tree,
  906.  *             if an adjacent record exists.
  907.  *
  908.  *    This is like _bt_step, except that if no adjacent record exists
  909.  *    it restores us to where we were before trying the step.  This is
  910.  *    only hairy when you cross page boundaries, since the page you cross
  911.  *    from could have records inserted or deleted, or could even split.
  912.  *    This is unlikely, but we try to handle it correctly here anyway.
  913.  *
  914.  *    This routine contains the only case in which our changes to Lehman
  915.  *    and Yao's algorithm.
  916.  *
  917.  *    Like step, this routine leaves the scan's currentItemData in the
  918.  *    proper state and acquires a lock and pin on *bufP.  If the twostep
  919.  *    succeeded, we return true; otherwise, we return false.
  920.  */
  921.  
  922. bool
  923. _bt_twostep(scan, bufP, dir)
  924.     IndexScanDesc scan;
  925.     Buffer *bufP;
  926.     ScanDirection dir;
  927. {
  928.     Page page;
  929.     BTPageOpaque opaque;
  930.     OffsetIndex offind, maxoff;
  931.     OffsetIndex start;
  932.     ItemPointer current;
  933.     ItemId itemid;
  934.     int itemsz;
  935.     BTItem btitem;
  936.     BTItem svitem;
  937.     BlockNumber blkno;
  938.  
  939.     blkno = BufferGetBlockNumber(*bufP);
  940.     page = BufferGetPage(*bufP, 0);
  941.     opaque = (BTPageOpaque) PageGetSpecialPointer(page);
  942.     maxoff = PageGetMaxOffsetIndex(page);
  943.     current = &(scan->currentItemData);
  944.     offind = ItemPointerGetOffsetNumber(current, 0) - 1;
  945.  
  946.     if (opaque->btpo_next != P_NONE)
  947.     start = 1;
  948.     else
  949.     start = 0;
  950.  
  951.     /* if we're safe, just do it */
  952.     if (ScanDirectionIsForward(dir) && offind < maxoff) {
  953.     ItemPointerSet(current, 0, blkno, 0, offind + 2);
  954.     return (true);
  955.     } else if (ScanDirectionIsBackward(dir) && offind < start) {
  956.     ItemPointerSet(current, 0, blkno, 0, offind);
  957.     return (true);
  958.     }
  959.  
  960.     /* if we've hit end of scan we don't have to do any work */
  961.     if (ScanDirectionIsForward(dir) && opaque->btpo_next == P_NONE)
  962.     return (false);
  963.     else if (ScanDirectionIsBackward(dir) && opaque->btpo_prev == P_NONE)
  964.     return (false);
  965.  
  966.     /*
  967.      *  Okay, it's off the page; let _bt_step() do the hard work, and we'll
  968.      *  try to remember where we were.  This is not guaranteed to work; this
  969.      *  is the only place in the code where concurrency can screw us up,
  970.      *  and it's because we want to be able to move in two directions in
  971.      *  the scan.
  972.      */
  973.  
  974.     itemid = PageGetItemId(page, offind);
  975.     itemsz = ItemIdGetLength(itemid);
  976.     btitem = (BTItem) PageGetItem(page, itemid);
  977.     svitem = (BTItem) palloc(itemsz);
  978.     bcopy((char *) btitem, (char *) svitem, itemsz);
  979.  
  980.     if (_bt_step(scan, bufP, dir)) {
  981.     pfree(svitem);
  982.     return (true);
  983.     }
  984.  
  985.     /* try to find our place again */
  986.     *bufP = _bt_getbuf(scan->relation, blkno, BT_READ);
  987.     page = BufferGetPage(*bufP, 0);
  988.     maxoff = PageGetMaxOffsetIndex(page);
  989.  
  990.     while (offind <= maxoff) {
  991.     itemid = PageGetItemId(page, offind);
  992.     btitem = (BTItem) PageGetItem(page, itemid);
  993.     if (btitem->bti_oid == svitem->bti_oid) {
  994.         pfree (svitem);
  995.         ItemPointerSet(current, 0, blkno, 0, offind + 1);
  996.         return (false);
  997.     }
  998.     }
  999.  
  1000.     /*
  1001.      *  XXX crash and burn -- can't find our place.  We can be a little
  1002.      *  smarter -- walk to the next page to the right, for example, since
  1003.      *  that's the only direction that splits happen in.  Deletions screw
  1004.      *  us up less often since they're only done by the vacuum daemon.
  1005.      */
  1006.  
  1007.     elog(WARN, "btree synchronization error:  concurrent update botched scan");
  1008.  
  1009.     /* NOTREACHED */
  1010. }
  1011.  
  1012. /*
  1013.  *  _bt_endpoint() -- Find the first or last key in the index.
  1014.  */
  1015.  
  1016. RetrieveIndexResult
  1017. _bt_endpoint(scan, dir)
  1018.     IndexScanDesc scan;
  1019.     ScanDirection dir;
  1020. {
  1021.     Relation rel;
  1022.     Buffer buf;
  1023.     Page page;
  1024.     BTPageOpaque opaque;
  1025.     ItemPointer current;
  1026.     ItemPointer iptr;
  1027.     OffsetIndex offind, maxoff;
  1028.     OffsetIndex start;
  1029.     BlockNumber blkno;
  1030.     BTItem btitem;
  1031.     IndexTuple itup;
  1032.     BTScanOpaque so;
  1033.     RetrieveIndexResult res;
  1034.  
  1035.     rel = scan->relation;
  1036.     current = &(scan->currentItemData);
  1037.  
  1038.     buf = _bt_getroot(rel, BT_READ);
  1039.     blkno = BufferGetBlockNumber(buf);
  1040.     page = BufferGetPage(buf, 0);
  1041.     opaque = (BTPageOpaque) PageGetSpecialPointer(page);
  1042.  
  1043.     for (;;) {
  1044.     if (opaque->btpo_flags & BTP_LEAF)
  1045.         break;
  1046.  
  1047.     if (ScanDirectionIsForward(dir)) {
  1048.         if (opaque->btpo_next == P_NONE)
  1049.         offind = 0;
  1050.         else
  1051.         offind = 1;
  1052.     } else
  1053.         offind = PageGetMaxOffsetIndex(page);
  1054.  
  1055.     btitem = (BTItem) PageGetItem(page, PageGetItemId(page, offind));
  1056.     itup = &(btitem->bti_itup);
  1057.  
  1058.     blkno = ItemPointerGetBlockNumber(&(itup->t_tid));
  1059.  
  1060.     _bt_relbuf(rel, buf, BT_READ);
  1061.     buf = _bt_getbuf(rel, blkno, BT_READ);
  1062.     page = BufferGetPage(buf, 0);
  1063.     opaque = (BTPageOpaque) PageGetSpecialPointer(page);
  1064.  
  1065.     /*
  1066.      *  Race condition:  If the child page we just stepped onto is in
  1067.      *  the process of being split, we need to make sure we're all the
  1068.      *  way at the edge of the tree.  See the paper by Lehman and Yao.
  1069.      */
  1070.  
  1071.     if (ScanDirectionIsBackward(dir) && opaque->btpo_next != P_NONE) {
  1072.         do {
  1073.         blkno = opaque->btpo_next;
  1074.         _bt_relbuf(rel, buf, BT_READ);
  1075.         buf = _bt_getbuf(rel, blkno, BT_READ);
  1076.         page = BufferGetPage(buf, 0);
  1077.         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
  1078.         } while (opaque->btpo_next != P_NONE);
  1079.     }
  1080.     }
  1081.  
  1082.     /* okay, we've got the {left,right}-most page in the tree */
  1083.     maxoff = PageGetMaxOffsetIndex(page);
  1084.  
  1085.     if (ScanDirectionIsForward(dir)) {
  1086.     if (PageIsEmpty(page))
  1087.         maxoff = 0;
  1088.     else
  1089.         maxoff = PageGetMaxOffsetIndex(page);
  1090.     if (opaque->btpo_next == P_NONE)
  1091.         start = 0;
  1092.     else
  1093.         start = 1;
  1094.  
  1095.     if (PageIsEmpty(page) || start > maxoff) {
  1096.         ItemPointerSet(current, 0, blkno, 0, maxoff + 1);
  1097.         if (!_bt_step(scan, &buf, BackwardScanDirection))
  1098.         return ((RetrieveIndexResult) NULL);
  1099.  
  1100.         start = ItemPointerGetOffsetNumber(current, 0);
  1101.         page = BufferGetPage(buf,0);
  1102.     } else {
  1103.         ItemPointerSet(current, 0, blkno, 0, start + 1);
  1104.     }
  1105.     } else if (ScanDirectionIsBackward(dir)) {
  1106.     if (PageIsEmpty(page)) {
  1107.         ItemPointerSet(current, 0, blkno, 0, 1);
  1108.         if (!_bt_step(scan, &buf, ForwardScanDirection))
  1109.         return ((RetrieveIndexResult) NULL);
  1110.  
  1111.         start = ItemPointerGetOffsetNumber(current, 0);
  1112.         page = BufferGetPage(buf,0);
  1113.     } else {
  1114.         start = PageGetMaxOffsetIndex(page);
  1115.         ItemPointerSet(current, 0, blkno, 0, start + 1);
  1116.     }
  1117.     } else {
  1118.     elog(WARN, "Illegal scan direction %d", dir);
  1119.     }
  1120.  
  1121.     btitem = (BTItem) PageGetItem(page, PageGetItemId(page, start));
  1122.     itup = &(btitem->bti_itup);
  1123.  
  1124.     /* see if we picked a winner */
  1125.     if (_bt_checkqual(scan, itup)) {
  1126.     iptr = (ItemPointer) palloc(sizeof(ItemPointerData));
  1127.     bcopy((char *) &(itup->t_tid), (char *) iptr, sizeof(ItemPointerData));
  1128.     res = ItemPointerFormRetrieveIndexResult(current, iptr);
  1129.  
  1130.     /* remember which buffer we have pinned */
  1131.     so = (BTScanOpaque) scan->opaque;
  1132.     so->btso_curbuf = buf;
  1133.     } else {
  1134.     _bt_relbuf(rel, buf, BT_READ);
  1135.     res = (RetrieveIndexResult) NULL;
  1136.     }
  1137.  
  1138.     return (res);
  1139. }
  1140.